/*************************************************************************
> File Name: insertion_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-20 09:05:18
> Description:插入排序
************************************************************************/
#include "general.h"
#include <stdio.h>

int insertionsort(int *arr, int length);

int main(int argc, char const *argv[])
{
    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    insertionsort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
    return 0;
}

int insertionsort(int *arr, int length)
{
    int i = 0, j = 0;
    int key = 0;
    for (i = 1; i < length; i++) // 1.从第二个开始、第一个数总是有序的
    {
        // 初始化
        key = *(arr + i);
        j = i - 1; // 从i-1开始判断是否移位
        // 调整位置
        while (j >= 0 && *(arr + j) > key) // 2.移动所有比他大的数，直到遇见一个小于等于他得数
        {
            *(arr + j + 1) = *(arr + j); // 3.移动的(  j+1 =j  截止在j)
            j--;
        }
        // 赋值    将他放在j+1的位置
        *(arr + j + 1) = key; // 4.由于前j个元素有序
    }
}